﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;
using System.IO;

namespace NETXPF.Library
{
    /// <summary>
    /// Provides high efficiency bit manipulation methods like counting the number of bits in a BitArray.
    /// Also includes bit-efficient encoding mechanisms like "VInts" which are variable-length integers (1, 2, 3, 4, or 5 bytes long).
    /// </summary>
    public class BitUtils
    {
        /// <summary>
        /// Creates a bit array with the specified length and fills it in with 'true' values for the specified range (from 'start' to 'end').
        /// </summary>
        /// <param name="start">First bit position to set to true</param>
        /// <param name="end">Last bit position to set to true</param>
        /// <param name="length">Length of the new bit array</param>
        /// <returns>New bit array filled in with 'true' for the specified range</returns>
        public static BitArray BitArrayForRange(int start, int end, int length)
        {
            int[] bitArray = new int[((length - 1) >> 5) + 1];

            Int32 startIndex = start >> 5;
            Int32 endIndex = end >> 5;
            UInt32 x = UInt32.MaxValue;

            bitArray[startIndex] = (int)(UInt32.MaxValue << (start & 31));

            for (Int32 i = startIndex + 1; i <= endIndex; i++)
            {
                bitArray[i] = (int)x;
            }

            bitArray[endIndex] &= (int)(UInt32.MaxValue >> (31 - (end & 31)));
            BitArray clrBitArray = new BitArray(bitArray);
            clrBitArray.Length = length;
            return clrBitArray;
        }

        public static bool HasTrueValues(BitArray bitArray)
        {
            int[] array = new int[((bitArray.Length - 1) >> 5) + 1];
            bitArray.CopyTo(array, 0);
            for (int i = 0; i < array.Length; i++)
            {
                if (array[i] != 0)
                {
                    return true;
                }
            }
            return false;
        }

        public static int CountBits(BitArray bitArray)
        {
            int cnt = 0;
            int[] array = new int[((bitArray.Length - 1) >> 5) + 1];
            bitArray.CopyTo(array, 0);
            for (int k = array.Length - 1; k >= 0; k--)
            {
                int i = array[k];
                if (k == array.Length - 1)
                {
                    i = i & (int)(UInt32.MaxValue >> (31 - ((bitArray.Length - 1) & 31)));
                }
                i = i - ((i >> 1) & 0x55555555);
                i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
                cnt += ((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
            }
            return cnt;
        }

        public static List<byte> EncodeVInt(int value)
        {
            List<byte> buf = new List<byte>();
            bool first = true;
            while (first || value > 0)
            {
                first = false;
                byte lower7bits = (byte)(value & 0x7f);
                value >>= 7;
                if (value > 0)
                    lower7bits |= 128;
                buf.Add(lower7bits);
            }
            return buf;
        }

        public static int DecodeVInt(BinaryReader br)
        {
            bool more = true;
            int value = 0;
            int shift = 0;
            while (more)
            {
                byte lower7bits = br.ReadByte();
                more = (lower7bits & 128) != 0;
                value |= (lower7bits & 0x7f) << shift;
                shift += 7;
            }
            return value;
        }
    }
}
